public class Sort {

    /**
     * 归并排序：
     * 时间复杂度：O(N*logN)
     * 空间复杂度：O(N)
     * 稳定性：稳定排序
     * @param array
     */
    public static void mergeSort(int[] array) {
        //merge(array,0, array.length - 1);
        mergeNor(array);
    }

    public static void merge(int[] array,int left,int right) {
        if(left >= right) {
            return;
        }

        int mid = (left + right)/2;
        merge(array,left,mid);
        merge(array,mid + 1,right);
        //走到这里 分解完毕
        //合并
        mergeArray(array,left,mid,right);
    }

    //合并的函数
    private static void mergeArray(int[] array, int left, int mid, int right) {
        //申请 right - left + 1 大小的数组
        int len = right - left + 1;
        int[] ret = new int[len];
        int k = 0;
        //递归回来：
        // left —— mid 是有序的
        // mid + 1 —— right 是有序的
        //相当于两个有序的数组，我们需要将两个有序数组合并成一个有序数组
        int s1 = left;
        //int e1 = mid;
        int s2 = mid + 1;
        //int e2 = right;

        while(s1 <= mid && s2 <= right) {
            //这里必须有 等于的情况，否则会陷入死循环
            if(array[s1] <= array[s2]) {
                ret[k++] = array[s1++];
            }
            if(array[s1] > array[s2]) {
                ret[k++] = array[s2++];
            }
        }
        while(s1 <= mid) {
            ret[k++] = array[s1++];
        }
        while (s2 <= right) {
            ret[k++] = array[s2++];
        }
        //上面代码实现完成后，就将所有元素都放入 ret 数组中

        //将 ret 中的有序数组写入 Array中
        for (int i = 0; i < k; i++) {
            //防止后面的将前面的 有序元素覆盖
            array[i + left] = ret[i];
        }
    }


    //归并排序的 非递归方法
    public static void mergeNor(int[] array) {
        //gap = 1是把每一个元素 看作一个有序的数组
        //gap 每次变成之前的二倍，相当于递归——归的过程
        int gap = 1;
        while(gap < array.length) {
            //for 循环，是把数组分为一个又一个 需要排序的区间
            //所以 i = i + gap * 2 是因为 i 到 i + gap * 2 之间是要排序的两个有序数组
            //这个归并排序的 非递归方法，有很多学习的地方，
            //可以多看看
            for (int i = 0; i < array.length; i = i = i + gap * 2) {
                int start = i;
                int mid = i + gap - 1;
                if(mid >= array.length) {
                    mid = array.length - 1;
                }
                int end = mid + gap;
                if(end >= array.length) {
                    end = array.length - 1;
                }

                mergeArray(array,start,mid,end);
            }
            gap *= 2;
        }
    }
}
